/*
 * Octree.java
 *
 * Created on October 6, 2007, 7:21 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */
package Raytracing.Accelerators;



import Raytracing.BoundingBox;
import Raytracing.Intersectable;
import Raytracing.Ray;
import Raytracing.StackElem;
import processing.core.*;
/**
 *
 * @author Matt
 */
public class KDTree extends Accelerator{
    
    private static final boolean DEBUG = false;

    public BoundingBox bounds;
    private KDTNode root;
    private int maxDepth = 30;
    private int maxSize = 10;
    StackElem [][] stack;
    public KDTree(){
        bounds = new BoundingBox(new PVector(1000,1000,1000),new PVector(-1000,-1000,-1000));
         /* stack required for traversal to store far children */
        stack = new StackElem[8][40];
        for (int i=0; i < 8; i++){
        for (int j=0; j < 40; j++){
            stack[i][j] = new StackElem();
        }
        }
    
    }
    
    public void validate(){
        Intersectable temp;
        
        //kill old tree if there was one
        root = new KDTNode();
        root.add(objects, maxSize, 1,maxDepth, bounds);  
        valid = true;        
        
    }
    
   
    public void add(Intersectable newObject) {
        
        //they've added an object, so the octree must be rebuilt before using
        valid = false;
        
        //put object in the renderlist
        objects.add(newObject);
        
        //make sure the extents are set properly
        bounds.contain(newObject);
        
    }
    
    public void draw(PApplet g) {
        

        Intersectable temp;
        /*
        for (int i = 0; i < objects.size(); i++ ){
            temp = (Intersectable)objects.get(i);
            temp.draw(g);
        }
        */
        if (showTree) root.draw(g);

    }
    public void draw(PApplet g, PVector camDirection) {
        

        Intersectable temp;
        for (int i = 0; i < objects.size(); i++ ){
            temp = (Intersectable)objects.get(i);
            temp.draw(g,camDirection);
        }
        
        if (showTree) root.draw(g);

    }    
    
    public boolean  findNearest(Ray ray, int ID) {

        //this portion from Havran's PHD Thesis
        //http://www.cgg.cvut.cz/u/havran/DISSVH/dissvh.pdf
              
        float a, b; /* entry/exit signed distance */
        float t; /* signed distance to the splitting plane */
       
        //check if ray intersects scene box

        if (!bounds.intersect(ray)){   
            return false;
        }

        a = ray.a;
        b = ray.b; 
       

        
        
        /* pointers to the far child node and current node */
        KDTNode farChild, currNode;
     
        currNode = root;/* start from the kd-tree root node */

        int enPt = 0; /* setup initial entry point . . . enPt corresponds to pointer */
        
        //create an item on the stack
        //stack[enPt] = new StackElem();
        stack[ID][enPt].t = a; /* set the signed distance */
        
        /* distinguish between internal and external origin */
        if (a >= 0.0f){ /* a ray with external origin */

            //TODO may be slow casting
            stack[ID][enPt].pb = ray.project(a);
        }
        else{ /* a ray with internal origin */

            stack[ID][enPt].pb = ray.origin.get();
        }

        
        /* setup initial exit point in the stack */
        int exPt = 1; /* pointer to the stack */
        stack[ID][exPt] = new StackElem();
        stack[ID][exPt].t = b;
        stack[ID][exPt].pb = ray.project(b);
        stack[ID][exPt].node = null; /* set termination flag */
        
        while(currNode != null){
            while (currNode.objList == null){
                if (DEBUG) System.out.println("Evaluating branch");
                float splitVal = currNode.splitPlane; 
                int axis = currNode.axis;
                //TODO: here be dragons

                if (getAxis(stack[ID][enPt].pb,axis) <= splitVal){
                    
                    if (getAxis(stack[ID][exPt].pb,axis) <= splitVal){

                    /* case N1, N2, N3, P5, Z2, and Z3 */
                        if (DEBUG) System.out.println("     Searching left   N1, N2, N3, P5, Z2, and Z3 ");
                        currNode = currNode.left;
                        continue;
                    }
                    if (getAxis(stack[ID][exPt].pb,axis) == splitVal){
                        if (DEBUG) System.out.println("     Searching right Z1");
                        currNode = currNode.right; 
                        continue; /* case Z1 */
                    }
                    /* if */
                    /* case N4 */
                        if (DEBUG) System.out.println("     Searching both N4");
                        farChild = currNode.right;
                        currNode = currNode.left;
                }
                else{
                   
                    /* (stack[enPt].pb[axis] > splitVal) */
                    if (splitVal < getAxis(stack[ID][exPt].pb,axis)){
                        /* case P1, P2, P3, and N5 */ 
                        if (DEBUG) System.out.println("     Searching right P1, P2, P3, and N5 ");
                        currNode = currNode.right;
                        continue;
                    }    
                    /* if */
                    if (DEBUG) System.out.println("     Searching both P4");
                    /* case P4*/
                    farChild = currNode.left;
                    currNode = currNode.right;
                } /* if */
                    /* case P4 or N4 . . . traverse both children */
                
                /* signed distance to the splitting plane */
                t = (splitVal - getAxis(ray.origin,axis)) / getAxis(ray.direction,axis);
                if (DEBUG) System.out.println("Split distance: " + t);
                /* setup the new exit point */
                int tmp = exPt;
                
                //Increment extpt
                exPt++;
          
                
                if (exPt == enPt){
                    exPt++;

                }
                //stack[exPt] = new StackElem();
                /* push values onto the stack */
                stack[ID][exPt].prev = tmp;
                stack[ID][exPt].t = t;
                stack[ID][exPt].node = farChild;
                setAxis(stack[ID][exPt].pb,axis,splitVal);

                
                int nextAxis = axis + 1 ;
                if (nextAxis == 3) nextAxis = 0;
                
                int prevAxis = axis-1;
                if (prevAxis == -1) prevAxis = 2;
                
                setAxis(stack[ID][exPt].pb,nextAxis,getAxis(ray.origin,nextAxis) + t * getAxis(ray.direction,nextAxis));
                setAxis(stack[ID][exPt].pb,prevAxis,getAxis(ray.origin,prevAxis) + t * getAxis(ray.direction,prevAxis));

                
            }/*while*/
            /* current node is the leaf . . . empty or full */

            if (currNode.procTerminal(ray, stack[ID][enPt].t, stack[ID][exPt].t)) return true;
            
            /* pop from the stack */
            enPt = exPt; /* the signed distance intervals are adjacent */
            
            /* retrieve the pointer to the next node, it is possible that ray traversal terminates */
            currNode = stack[ID][exPt].node;
            
            exPt = stack[ID][enPt].prev;
            
        }/*while*/
        /* currNode = nowhere, ray leaves the scene */

        return false;       


    }
    
      
    
    public float getAxis(PVector vector, int axis){
        switch (axis){
            case 0: return vector.x;
            case 1: return vector.y;
            case 2: return vector.z;
            
        }
        return -1;
    }
    public void setAxis(PVector vector, int axis,float val){
       
        switch (axis){
            case 0: vector.x = val;
                break;
            case 1: vector.y = val;
                break;
            case 2: vector.z = val;
                break;
    
        }

    }
    
    
    
    
    
    
}
